package pl.poznan.put.cs.to.tsp.hea;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
import java.util.Set;

import pl.poznan.put.cs.to.tsp.common.IResultHolder;
import pl.poznan.put.cs.to.tsp.common.Vertexes;
import pl.poznan.put.cs.to.tsp.localsearch.Edge;

public class ResultCrosser implements IResultHolder {
	private IResultHolder firstResult;
	private IResultHolder secondResult;

	private LinkedList<Integer> listA;
	private LinkedList<Integer> listB;
	private int lengthA;
	private int lengthB;
	private Vertexes vertexes;

	private Set<Edge> commonEdges;
	private List<Integer> availableVertexes;
	private int[] vertexCountVector;
	private int[][] vertexNeighbours;

	private Set<Integer> setA;
	private Set<Integer> setB;
	private Set<Integer> rest;

	private int sameInA;
	private int sameInB;

	public ResultCrosser(IResultHolder firstResult, IResultHolder secondResult,
			Vertexes vertexes) {
		this.firstResult = firstResult;
		this.secondResult = secondResult;
		this.vertexes = vertexes;

		System.out.println("===== BEFORE CROSSING ======");
		System.out.println("Result 1/A:");
		this.printList(this.firstResult.getListA());
		System.out.println("Result 1/B:");
		this.printList(this.firstResult.getListB());
		System.out.println("Result 2/A:");
		this.printList(this.secondResult.getListA());
		System.out.println("Result 2/B:");
		this.printList(this.secondResult.getListB());

		this.initialize();

		Set<Edge> transformedA = this
				.transformResultToEdgeSet(this.firstResult);
		this.compareResults(transformedA, this.secondResult);

		this.crossResults();

		System.out.println("===== CROSSING RESULT! =======");
		System.out.println("A:");
		this.printList(this.listA);
		System.out.println("B:");
		this.printList(this.listB);
		System.out.println("\t\tCROSSED!");

		this.checkResult();
	}

	private void checkResult() {
		boolean correct = true;

		int properLength = this.firstResult.getListA().size()
				+ this.firstResult.getListB().size();
		int actualLength = this.listA.size() + this.listB.size();
		if (actualLength != properLength) {
			System.out.println(properLength + " | " + actualLength);
			correct = false;
		}

		for (int i : this.listA) {
			int repeats = 0;
			for (int j : this.listA) {
				if (i == j) {
					repeats++;
				}
			}
			for (int j : this.listB) {
				if (i == j) {
					repeats++;
				}
			}
			if (repeats > 1) {
				System.out.println(i + " - " + (repeats - 1) + " repeats");
				correct = false;
			}
		}

		for (int i : this.listB) {
			int repeats = 0;
			for (int j : this.listA) {
				if (i == j) {
					repeats++;
				}
			}
			for (int j : this.listB) {
				if (i == j) {
					repeats++;
				}
			}
			if (repeats > 1) {
				System.out.println(i + " - " + (repeats - 1) + " repeats");
				correct = false;
			}
		}

		if (!correct) {
			throw new RuntimeException("Crossing failed!");
		}
	}

	private void printList(List<Integer> list) {
		for (int i : list) {
			System.out.print(i + " ");
		}
		System.out.println();
		System.out.println("n = " + list.size());
	}

	private void printVNVector() {
		for (int i = 0; i < this.vertexCountVector.length; i++) {
			System.out.print(i + ": ");
			for (int j = 0; j < 2; j++) {
				System.out.print(this.vertexNeighbours[i][j] + " ");
			}
			System.out.println();
		}
	}

	private void crossResults() {
		// this.printVCountVector();

		if (this.sameInA == this.firstResult.getListA().size()
				&& this.sameInB == this.firstResult.getListB().size()) {
			this.listA = this.firstResult.getListA();
			this.listB = this.firstResult.getListB();
			this.lengthA = this.firstResult.getLengthA();
			this.lengthB = this.firstResult.getLengthB();
			return;
		}
		if (this.sameInA == this.firstResult.getListA().size()) {
			this.listA = this.firstResult.getListA();
			this.lengthA = this.firstResult.getLengthA();
			for (int i : this.listA) {
				this.vertexNeighbours[i][0] = -1;
				this.vertexNeighbours[i][1] = -1;
				int index = this.availableVertexes.indexOf(i);
				if (index != -1) {
					this.availableVertexes.remove(index);
				}
			}
			this.listB = this.generateOneList();
			this.lengthB = this.calculateLength(this.listB);
			return;
		}
		if (this.sameInB == this.firstResult.getListB().size()) {
			this.listA = this.firstResult.getListB();
			this.lengthA = this.firstResult.getLengthB();
			for (int i : this.listA) {
				this.vertexNeighbours[i][0] = -1;
				this.vertexNeighbours[i][1] = -1;
				int index = this.availableVertexes.indexOf(i);
				if (index != -1) {
					this.availableVertexes.remove(index);
				}
			}
			this.listB = this.generateOneList();
			this.lengthB = this.calculateLength(this.listB);
			return;
		}

		this.generateBothLists();
	}

	private void generateBothLists() {
		boolean toA;
		Random r = new Random();
		int drawn;
		int v;

		while (!this.availableVertexes.isEmpty()) {
			drawn = r.nextInt(this.availableVertexes.size());
			v = this.availableVertexes.remove(drawn);
			toA = r.nextBoolean();

			if (this.vertexCountVector[v] == 1) {
				LinkedList<Integer> part = this.processPathPart(v);
				// System.out.println("part:");
				// this.printList(part);
				if (toA) {
					this.listA.addAll(part);
				} else {
					this.listB.addAll(part);
				}
			} else if (this.vertexCountVector[v] == 0) {
				if (toA) {
					this.listA.add(v);
				} else {
					this.listB.add(v);
				}
			}
			/*
			 * System.out.println("----------------------------------");
			 * System.out.println("A:"); this.printList(this.listA);
			 * System.out.println("B:"); this.printList(this.listB);
			 * System.out.println("availableVertexes:");
			 * this.printList(this.availableVertexes);
			 * System.out.println("----------------------------------");
			 */
			// this.printVCountVector();
		}

		this.lengthA = this.calculateLength(this.listA);
		this.lengthB = this.calculateLength(this.listB);
	}

	private int calculateLength(LinkedList<Integer> list) {
		int distance = 0;
		if (list.size() == 0) {
			return 0;
		}
		int first = list.getFirst();
		int last = list.getLast();
		int before = -1;

		for (Integer i : list) {
			if (before == -1) {
				distance += this.vertexes.getDistanceBetween(first, last);
			} else {
				distance += this.vertexes.getDistanceBetween(before, i);
			}
			before = i;
		}

		return distance;
	}

	private LinkedList<Integer> generateOneList() {
		LinkedList<Integer> list = new LinkedList<Integer>();
		Random r = new Random();
		int drawn;
		int v;
		boolean atBeginning; // czy dolaczac na poczatku czy na koncu
		// listy-wyniku

		while (!this.availableVertexes.isEmpty()) {
			drawn = r.nextInt(this.availableVertexes.size());
			v = this.availableVertexes.remove(drawn);
			atBeginning = r.nextBoolean();

			if (this.vertexCountVector[v] == 1) {
				LinkedList<Integer> part = this.processPathPart(v);
				list.addAll(part);
			} else if (this.vertexCountVector[v] == 0) {
				list.add(v);
			}
			/*
			 * System.out.println(":::::::::::::::::::::::::::::::::::");
			 * System.out.println("A:"); this.printList(this.listA);
			 * System.out.println("B:"); this.printList(this.listB);
			 * System.out.println("tempList:"); this.printList(list);
			 * System.out.println("availableVertexes:");
			 * this.printList(this.availableVertexes);
			 * System.out.println(":::::::::::::::::::::::::::::::::::");
			 */
		}

		return list;
	}

	private LinkedList<Integer> processPathPart(int first) {
		LinkedList<Integer> res = new LinkedList<Integer>();

		int actual = first;
		int next = this.findNeighbourForVertex(actual);
		/*
		 * System.out.println(); this.printVNVector(); System.out.println();
		 */
		while (next >= 0) {
			// System.out.println("actual = " + actual);
			// System.out.println("next = " + next);
			res.add(actual);
			for (int i = 0; i < 2; i++) {
				if (this.vertexNeighbours[actual][i] == next) {
					this.vertexNeighbours[actual][i] = -1;
				}
				if (this.vertexNeighbours[next][i] == actual) {
					this.vertexNeighbours[next][i] = -1;
				}
			}
			actual = next;
			next = this.findNeighbourForVertex(actual);
		}

		res.add(actual);
		this.availableVertexes.remove(this.availableVertexes.indexOf(Integer
				.valueOf(actual)));

		return res;
	}

	private int findNeighbourForVertex(int v) {
		int res = this.vertexNeighbours[v][0];
		if (res >= 0) {
			return res;
		}
		res = this.vertexNeighbours[v][1];
		if (res >= 0) {
			return res;
		}
		return -1;
	}

	private void compareResults(Set<Edge> res1, IResultHolder res2) {
		// System.out.println(res1);
		int prev;

		if (res2.getListA().size() == 1) {

		} else if (res2.getListA().size() == 2) {
			Edge e = new Edge(res2.getListA().getFirst(), res2.getListA()
					.getLast());
			// System.out.print(e + " ");
			int first = res2.getListA().getFirst();
			int last = res2.getListA().getLast();
			if (res1.contains(e)) {
				// System.out.print("x");
				this.commonEdges.add(e);
				this.vertexCountVector[first]++;
				this.vertexCountVector[last]++;
				if (this.vertexNeighbours[first][0] < 0) {
					this.vertexNeighbours[first][0] = last;
				} else {
					this.vertexNeighbours[first][1] = last;
				}
				if (this.vertexNeighbours[last][0] < 0) {
					this.vertexNeighbours[last][0] = first;
				} else {
					this.vertexNeighbours[last][1] = first;
				}
				this.sameInA++;
			}
			// System.out.println();
		} else {
			prev = res2.getListA().getLast();
			for (int i : res2.getListA()) {
				Edge e = new Edge(prev, i);
				// System.out.print(e + " ");
				if (res1.contains(e)) {
					// System.out.print("x");
					this.commonEdges.add(e);
					this.vertexCountVector[prev]++;
					this.vertexCountVector[i]++;
					if (this.vertexNeighbours[prev][0] < 0) {
						this.vertexNeighbours[prev][0] = i;
					} else {
						this.vertexNeighbours[prev][1] = i;
					}
					if (this.vertexNeighbours[i][0] < 0) {
						this.vertexNeighbours[i][0] = prev;
					} else {
						this.vertexNeighbours[i][1] = prev;
					}
					this.sameInA++;
				}
				prev = i;
				// System.out.println();
			}
		}

		if (res2.getListB().size() == 1) {

		} else if (res2.getListB().size() == 2) {
			Edge e = new Edge(res2.getListB().getFirst(), res2.getListB()
					.getLast());
			int first = res2.getListB().getFirst();
			int last = res2.getListB().getLast();
			// System.out.print(e + " ");
			if (res1.contains(e)) {
				// System.out.print("x");
				this.commonEdges.add(e);
				this.vertexCountVector[first]++;
				this.vertexCountVector[last]++;
				if (this.vertexNeighbours[first][0] < 0) {
					this.vertexNeighbours[first][0] = last;
				} else {
					this.vertexNeighbours[first][1] = last;
				}
				if (this.vertexNeighbours[last][0] < 0) {
					this.vertexNeighbours[last][0] = first;
				} else {
					this.vertexNeighbours[last][1] = first;
				}
				this.sameInB++;
			}
			// System.out.println();
		} else {
			prev = res2.getListB().getLast();
			for (int i : res2.getListB()) {
				Edge e = new Edge(prev, i);
				// System.out.print(e + " ");
				if (res1.contains(e)) {
					// System.out.print("x");
					this.commonEdges.add(e);
					this.vertexCountVector[prev]++;
					this.vertexCountVector[i]++;
					if (this.vertexNeighbours[prev][0] < 0) {
						this.vertexNeighbours[prev][0] = i;
					} else {
						this.vertexNeighbours[prev][1] = i;
					}
					if (this.vertexNeighbours[i][0] < 0) {
						this.vertexNeighbours[i][0] = prev;
					} else {
						this.vertexNeighbours[i][1] = prev;
					}
					this.sameInB++;
				}
				prev = i;
				// System.out.println();
			}
		}

		for (int i = 0; i < this.vertexCountVector.length; i++) {
			if (this.vertexCountVector[i] < 2) {
				this.availableVertexes.add(i);
			}
		}
	}

	private void findCommonVertexesSets(IResultHolder firstResult,
			IResultHolder secondResult) {
		this.setA = new HashSet<Integer>();
		this.setB = new HashSet<Integer>();
		this.rest = new HashSet<Integer>();
		Set<Integer> setA1 = new HashSet<Integer>(firstResult.getListA());
		Set<Integer> setA2 = new HashSet<Integer>(secondResult.getListA());
		Set<Integer> setB1 = new HashSet<Integer>(firstResult.getListB());
		Set<Integer> setB2 = new HashSet<Integer>(secondResult.getListB());
		int similarityAA = this.findSimilarity(setA1, setA2)
				+ this.findSimilarity(setB1, setB2);
		int similarityAB = this.findSimilarity(setA1, setB2)
				+ this.findSimilarity(setB1, setA2);
		if (similarityAA > similarityAB) {
			this.fillCommonVertexes(setA, setA1, setA2);
			this.fillCommonVertexes(setB, setB1, setB2);
		} else {
			this.fillCommonVertexes(setA, setA1, setB2);
			this.fillCommonVertexes(setB, setB1, setA2);
		}
		this.addRest(rest, setA1, setA, setB);
		this.addRest(rest, setA2, setA, setB);
	}

	private void addRest(Set<Integer> rest, Set<Integer> set,
			Set<Integer> set1, Set<Integer> set2) {
		for (Integer i : set) {
			if (!set1.contains(i) && !set2.contains(i)) {
				rest.add(i);
			}
		}
	}

	private void fillCommonVertexes(Set<Integer> common, Set<Integer> set1,
			Set<Integer> set2) {
		for (Integer i : set1) {
			if (set2.contains(i)) {
				common.add(i);
			}
		}
	}

	private int findSimilarity(Set<Integer> set1, Set<Integer> set2) {
		int count = 0;
		for (Integer i : set1) {
			if (set2.contains(i)) {
				count = count + 1;
			}
		}
		return count;
	}

	private void initialize() {
		this.commonEdges = new HashSet<Edge>();
		this.availableVertexes = new ArrayList<Integer>();
		this.vertexCountVector = new int[this.firstResult.getListA().size()
				+ this.firstResult.getListB().size()];
		this.vertexNeighbours = new int[this.firstResult.getListA().size()
				+ this.firstResult.getListB().size()][2];

		for (int i = 0; i < this.vertexNeighbours.length; i++) {
			for (int j = 0; j < 2; j++) {
				this.vertexNeighbours[i][j] = -1;
			}
		}

		this.listA = new LinkedList<Integer>();
		this.listB = new LinkedList<Integer>();

		this.sameInA = 0;
		this.sameInB = 0;

		this.findCommonVertexesSets(this.firstResult, this.secondResult);
	}

	private Set<Edge> transformResultToEdgeSet(IResultHolder result) {
		Set<Edge> out = new HashSet<Edge>();
		int prev;

		if (result.getListA().size() > 1) {
			prev = result.getListA().getLast();
			for (int i : result.getListA()) {
				out.add(new Edge(i, prev));
				prev = i;
			}
		}

		if (result.getListB().size() > 1) {
			prev = result.getListB().getLast();
			for (int i : result.getListB()) {
				out.add(new Edge(i, prev));
				prev = i;
			}
		}

		return out;
	}

	@Override
	public int getLengthA() {
		return this.lengthA;
	}

	@Override
	public int getLengthB() {
		return this.lengthB;
	}

	@Override
	public LinkedList<Integer> getListA() {
		return this.listA;
	}

	@Override
	public LinkedList<Integer> getListB() {
		return this.listB;
	}

	@Override
	public Vertexes getVertexes() {
		return this.vertexes;
	}

	@Override
	public int compareTo(IResultHolder o) {
		int local = this.getLengthA() + this.getLengthB();
		int other = o.getLengthA() + o.getLengthB();
		return local - other;
	}
}
